//
// Created by Vincent-Vic on 2020/3/19.
//

#ifndef DATAORGANIZATION_BINARYSEARCHTREE_H
#define DATAORGANIZATION_BINARYSEARCHTREE_H
//深度优先遍历(DFS)和广度优先遍历(BFS)
#include <iostream>
#include <queue>
#include <cassert>
using namespace std;
template <typename Key,typename Value>
class BinarySearchTree {
private:
    struct Node{
        Key key;
        Value value;
        Node* left;
        Node* right;

        Node(Key key,Value value){
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }
        //拷贝函数
        Node(Node* node){
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
        }
    };

    Node * root; //树根
    int count;  //个数

    /**
     * 以node为根递归插入
     * 形成左小右达到二叉树逻辑
     * @param node 假设当前是根节点
     * @param key
     * @param value
     * @return 新的节点或者修改的点
     */
    Node* insert(Node* node , Key key , Value value){
        if (node == NULL){  //递归结束条件：当前节点为空，将节点插入
            count ++;   //节点增加
            return new Node(key,value); //创建新节点
        }
         if( key == node->key)  //如果key已经存在，替换key旧的值value
             node->value = value;
         else if(key < node->key) //key小于当前节点key 从左子树递归插入
             node->left = insert(node->left,key,value);
         else   //此时key大于当前节点key，向右子树递归插入
             node->right = insert(node->right,key,value);

        return node;
    }

    /**
     * 以node为根的二叉树中判断树中是否包含键值key的节点
     * @param node
     * @param key
     * @return
     */
    bool contain(Node* node,Key key){
        if (node == NULL) return false;
        if (key == node->key)   //如果键值与当前相等说明存在返回true
            return true;
        else if(key < node->key) //key 小于当前节点key 从左子树递归查找判断key是否存在
            return contain(node->left,key);
        else   //此时key大于当前节点key，向右子树递归查找判断key是否存在
            return contain(node->right,key);
    }

    /**
     * 以node为根的二叉树中查找节点
     * @param node
     * @param key
     * @return value地址
     */
    Value* search(Node* node,Key key){
        if (node == NULL)
            return NULL;

        if ( key == node->key)
            return &(node->value);
        else if(key < node->key) //key 小于当前节点key 从左子树递归查找判断key是否存在
            return search(node->left,key);
        else   //此时key大于当前节点key，向右子树递归查找判断key是否存在
            return search(node->right,key);

    }


    /**
     * 以node为根的二叉树 进行先序遍历
     * @param node
     */
    void preOrder(Node* node){
        if (node != NULL){
            cout<<node->key <<endl;
            preOrder(node->left);
            preOrder(node->right);
        }

    }

    /**
     * 以node为根的二叉树 进行中序遍历 有序遍历二分搜索树
     * @param node
     */
    void inOrder(Node* node){
        if (node != NULL){
            inOrder(node->left);
            cout<<node->key <<endl;
            inOrder(node->right);
        }

    }

    /**
     * 以node为根的二叉树 进行后续遍历
     * @param node
     */
    void postOrder(Node* node){
        if (node != NULL){
            postOrder(node->left);
            postOrder(node->right);
            cout<<node->key <<endl;
        }

    }

    /**
    * 以node为根的二叉树 查找最大值
    * @param node
    */
    Node* maximum(Node* node){
        if (node->right == NULL)    //如果右节点不存在，当前节点即最大
            return node;
        return maximum(node->right); //存在右节点继续递归查找
    }

    /**
    * 以node为根的二叉树 查找最小值
    * @param node
    */
    Node* minimum(Node* node){
        if (node->left == NULL) //如果左节点不存在，当前节点即最小
            return node;
        return minimum(node->left); //存在左节点继续递归查找
    }

    /**
    * 以node为根的二叉树 删除最小值
    * @param node
    */
    Node* removeMin(Node* node){
        if (node->left == NULL) {   //如果左节点不存在，当前节点即最小
            Node* right = node->right ; //取用右节点代替
            delete node;    //删除节点 释放内存
            node = NULL;
            count --; //减少节点
            return right; //返回右节点作为最小节点或者NULL
        }
        node->left = removeMin(node->left); //递归删除
        return node;
    }

    /**
    * 以node为根的二叉树 删除最大值
    * @param node
    */
    Node* removeMax(Node* node){
        if (node->right == NULL) {   //如果右节点不存在，当前节点即最大
            Node* left = node->left ; //取用左节点代替
            delete node;    //删除节点 释放内存
            node = NULL;
            count --; //减少节点
            return left; //返回左节点作为最小节点或者NULL
        }
        node->right = removeMax(node->right); //递归
        return node;
    }

    //删除节点  Hubbard Deletion思想
    /**
    * 以node为根的二叉树 删除Key节点
    * @param node
    */
    Node* remove(Node* node,Key key){
        if (node == NULL) return NULL;
        if (key < node->key)  //左数查找
            node->left = remove(node->left,key);
        else if (key > node->key)   //右树查找
            node->right = remove(node->right,key);
        else{ //找到的情况
            if (node->left == NULL){    //左孩子为空以及左右孩子都为空
                Node* right = node->right; //右节点代替左节点的位置
                delete node;
                count --;
                return right;
            }
            if (node->right == NULL){ //右孩子为空
                Node* left = node->left;//左节点代替右节点的位置
                delete node;
                count --;
                return left;
            }
            //处理左右子树都存在的情况
            Node* successor = new Node(minimum(node->right)); //找到右子树的最小值替换删除的节点（拷贝）
            successor->right = removeMin(node->right);  //替换节点指向删除右子树最小值后的右子树（已经用来替换的节点）
            successor->left = node->left;   //替换节点指向用来左子树
            delete  node;
            node = NULL;
            return successor; //返回新树
        }
        return node;

    }

public:

    BinarySearchTree() {
        root = NULL;
        count = 0;
    }

    BinarySearchTree(Node* node) {}

    virtual ~BinarySearchTree() {
        destroy(root);
    }

    //树的数量
    int size(){
        return count;
    }

    //是否为空
    bool isEmpty(){
        return count ==0;
    }

    //插入
    void insert(Key key,Value value){
        root = insert(root,key,value);
    }

    //判断键值是否存在
    bool contain(Key key){
        return contain(root,key);
    }

    //查找
    Value* search(Key key){
        return search(root,key);
    }

    //深度优先遍历(DFS) 先序遍历
    void preOrder(){
        preOrder(root);
    }

    //深度优先遍历(DFS) 中序遍历 有序遍历二分搜索树
    void inOrder(){
        inOrder(root);
    }

    //深度优先遍历(DFS) 后续遍历
    void postOrder(){
        postOrder(root);
    }

    //广度优先遍历(BFS) 层次遍历-队列实现
    void levelOrder(){
        queue<Node*> q; //存放Node的队列
        if (root == NULL){  //判断树空的情况
            cout<<"Tree Null"<<endl;
            return;
        }
        q.push(root);
        while ( !q.empty()){
            Node* node = q.front(); //取出第一个值
            q.pop(); //将第一个值出队，以便遍历下一个值
            cout<<node->key<<endl; //打印key值
            if (node->left) //如果左节点存在加入左子树的节点
                q.push(node->left);
            if (node->right) //如果右节点存在加入右子树的节点
                q.push(node->right);
        }

    }

    //查找最大值
    Key maximum(){
        assert( count != 0);
        Node* maxNode = maximum( root);
        return maxNode->key;
    }

    //查找最小值
    Key minimum(){
        assert( count != 0);
        Node* minNode = minimum( root);
        return minNode->key;
    }

    //删除最小值
    void removeMin(){
        if (root)
            root = removeMin(root);
    }

    //删除最大值
    void removeMax(){
        if (root)
            root = removeMax(root);
    }

    //删除节点  Hubbard Deletion思想
    void remove(Key key){
        root = remove(root,key);
    }


    //销毁树 后序遍历的应用
    void destroy(Node* node){
        if (node != NULL){
            destroy(node->left);
            destroy(node->right);
            delete  node;
            node = NULL;
            count --;
        }
    }

};

//floor ceil rank select

#endif //DATAORGANIZATION_BINARYSEARCHTREE_H
